Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol (IP) packets, Ethernet frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the network elements. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, how protocol data units should be handled or routed through the network by the network elements, and how information such as routing information should be exchanged between the network elements.
Ethernet is a well known networking protocol that has been defined by the Institute of Electrical and Electronics Engineers (IEEE) as standard 802.3, and as 802.1 for Ethernet bridging functionality. In Ethernet network architectures, devices connected to the network compete for the ability to use shared telecommunications paths at any given time. Where multiple bridges or nodes are used to interconnect network segments, multiple potential paths to the same destination often exist. The benefit of this architecture is that it provides path redundancy between bridges and permits capacity to be added to the network in the form of additional links. However to prevent loops from being formed, a spanning tree was generally used to restrict the manner in which traffic was broadcast or flooded on the network. A characteristic of spanning tree is that there is only one path between any pair of destinations in the network, and therefore it was possible to “learn” the connectivity associated with a given spanning tree by where packets came from. However, the spanning tree itself was restrictive and often led to over-utilization of the links that were on the spanning tree and non-utilization of the links that weren't part of the spanning tree.
To overcome some of the limitations inherent in Ethernet networks, a link state protocol controlled Ethernet network was disclosed in application Ser. No. 11/537,775, filed Oct. 2, 2006, entitled “Provider Link State Bridging,” the content of which is hereby incorporated herein by reference. As described in greater detail in that application, rather than utilizing a learned network view at each node by using the Spanning Tree Protocol (STP) algorithm combined with transparent bridging, in a link state protocol controlled Ethernet network the bridges forming the mesh network exchange link state advertisements to enable each node to have a synchronized view of the network topology. This is achieved via the well understood mechanism of a link state routing system. A Provider Link State Bridging network preferably uses “MAC-in-MAC” encapsulation as defined in IEEE 802.1ah, to completely separate the customer (C-MAC) address space from the provider (B-MAC) address space, so that the link state routing system is exposed only to B-MAC addresses which are assigned under provider control. With the use of MAC-in-MAC encapsulation, the bridges in the network have a synchronized view of the network topology, have knowledge of the requisite unicast and multicast connectivity, can compute a shortest path connectivity between any pair of bridges in the network, and individually can populate their forwarding information bases (FIBs) according to the computed view of the network, all in terms of provider-administered B-MAC addresses only.
When all nodes have computed their role in the synchronized view and populated their FIBs, the network will have a loop-free unicast tree to any given bridge from the set of peer bridges (those that require communication to that bridge for whatever reason); and a both congruent and loop-free point-to-multipoint (P2MP) multicast tree from any given bridge to the same set or subset of peer bridges per service instance hosted at the bridge. The result is the path between a given bridge pair is not constrained to transiting the root bridge of a spanning tree and the overall result can better utilize the breadth of connectivity of a mesh. In essence every bridge roots one or more trees which define unicast connectivity to that bridge, and multicast connectivity from that bridge.
When customer traffic enters a provider network, the customer MAC address (C-MAC DA) is resolved to a provider MAC address (B-MAC DA), so that the provider may forward traffic on the provider network using the provider MAC address space. Additionally, the network elements on the provider network are configured to forward traffic based on Virtual LAN ID (VID) so that different frames addressed to the same destination address but having different VIDs may be forwarded over different paths through the network. In operation, a link state protocol controlled Ethernet network may associate one VID range with shortest path forwarding, such that unicast and multicast traffic may be forwarded using a VID from that range, and traffic engineering paths may be created across the network on paths other than the shortest path, and forwarded using a second VID range.
Two examples of link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS), although other link state routing protocols may be used as well. IS-IS is described, for example, in ISO 10589, and IETF RFC 1195, the content of each of which is hereby incorporated herein by reference.
In addition to installing shortest path unicast forwarding state, the nodes may also install forwarding state for multicast trees on the network. An example of a way to implement multicast in a link state protocol controlled Ethernet network is described in greater detail in U.S. patent application Ser. No. 11/702,263, filed Feb. 5, 2007, entitled “Multicast Implementation in a Link State Protocol Controlled Ethernet Network” the content of which is hereby incorporated herein by reference. As described in that application, link state advertisements may be used to advertise multicast group membership to cause forwarding state for a multicast group to be installed on the network. In particular, each source for a given multicast group may be assigned a destination MAC Address (DA) that is used to forward the frames on the network. The nodes on the network install forwarding state for the source/group tree if they determine that they are on a shortest path from the multicast source to at least one of the destination nodes advertising via the link state protocol an “interest” in the multicast group.
Interest in a multicast may be based on the community of interest identifier such as the I-SID, such that a node on the network will install forwarding state for a multicast group when it is on a shortest path between a source and destination that have both advertised interest in the community of interest identifier associated with the multicast group. An I-SID normally is associated with 802.1 ah and implies an additional MAC header (customer source & destination MAC addresses). The utility of the I-SID without the C-MAC header is well understood and is assumed herein. The forwarding state, however, is based on the multicast DA and VID associated with the multicast. In operation, multiple nodes on the network may advertise interest in a particular I-SID. The nodes on the network keep track of which nodes have advertised interest in which I-SID and will install forwarding state for a DA/VID pair associated with the I-SID if they are on the shortest path between two nodes that have advertised interest in the particular I-SID. This allows forwarding state to be installed for communities of interest without requiring flooding of the frames on the network.
Link state protocol controlled Ethernet networks operate at the link layer (Layer 2). That is, the ingress node creates a MAC header that may be used to switch the frame across the Ethernet network, e.g. from Node A to Node E. Other networks, such as Internet Protocol (IP) networks, operate at a higher layer such as Layer 3 (network layer). IP networks forward packets based on an IP address of an IP header associated with an IP packet. In a conventional IP network, an IP lookup is performed at each hop through the network. That is, each node will strip off the outer Ethernet header, read the IP header, and do an IP lookup to route the packet through the network. The node will then add a new Ethernet header to forward the packet to the next node on the network.
FIG. 1 shows how IP forwarding occurs in a multi-protocol label switching (MPLS) network. MPLS networks reduce the number of IP lookups that are required to be performed at the various routers in the network. In an MPLS network, a plurality of Label Switched Paths (LSPs) will be established through the MPLS network. The particular manner in which LSPs are determined and created through the network is well known. In the example shown in FIG. 1 it will be assumed that the label switched path includes nodes A, B, C, D, E. When a packet arrives at the edge router 22A from network X, the edge router 22A will perform an IP lookup to determine which label should be used to switch the IP packet onto the LSP through the MPLS network to reach network Y. The edge router 22A will also determine a next hop for the packet on the path and apply a MAC header to the packet to cause the packet to be forwarded to the next hop on the path (router 22B).
Router 22B will strip the outer MAC header and read the MPLS label. When the LSP was established through the network the label distribution protocol will have established an association between labels on the path, such that for example an association may be formed between label 100 and label 210 for a particular IP Forwarding Equivalence Class. The label association allows the routers to use the label to forward the packet instead of performing an IP lookup. Thus, for example, when the router 22B receives a packet with MPLS label 100, it will replace the label with a new MPLS label 210 and forward the packet to the outbound interface. Before forwarding the packet, router 22B will add a new MAC header to the packet which, in this instance, is SA=J, DA=K to identify the source MAC address as MAC J on router 22B and the destination MAC address as MAC K on router 22C. This process will be repeated at each hop along the label switched path until the packet reaches the label edge router (Node E).
MPLS thus allows a single IP route lookup to be performed at the edge of the MPLS network, and allows label switching to be used instead of IP lookups to forward the packet across the MPLS network. Edge routers that perform the initial IP lookup and assign the label to the packet to place the packet on the LSP are referred to as Label Edge Routers (LERs). Intermediate routers on the MPLS network that perform label switching are commonly referred to as Label Switch Routers (LSRs). Forwarding in an MPLS network is performed by swapping a label after stripping the MAC header at each hop. MPLS forwarding still requires MAC header stripping to occur at every hop across the network (when Ethernet links are employed), requires each LSR to perform a label lookup and label swap, and requires each LSR to then add another MAC header to deliver the packet to the next LSR along the LSP. This process requires processing and intelligence on each of the nodes which thus results in an expensive solution. Additionally, for this to work, the LSP must be initially set up which in and of itself is a computationally expensive process.
A way to enable a link state protocol controlled Ethernet network to implement network layer forwarding was disclosed in U.S. patent application Ser. No. 12/006,258, filed Dec. 31, 2007, entitled “IP Forwarding Across A Link State Protocol Controlled Ethernet Network,” the content of which is hereby incorporated herein by reference. Additionally, a way to enable a link state protocol controlled Ethernet network to replace the label switch routers in an MPLS network was disclosed in U.S. patent application Ser. No. 12/006,257, filed Dec. 31, 2007, entitled “MPLS Node Replacement Using A Link State Protocol Controlled Ethernet Network”, the content of which is likewise hereby incorporated herein by reference.
Since many customers may share a provider's network, techniques have been developed to allow one customer's data to be segregated from another customer's data. Conventionally, this is implemented using a Virtual Private Network. FIG. 2 shows an example MPLS network in which one or more Virtual Private Networks (VPNs) have been established across the network. A VPN may be established on an MPLS network using the procedures set forth in Internet Engineering Task Force (IETF) Request For Comments (RFC) 4364 for IPv4 VPNs, or RFC 4659 for IPv6 VPNs. Briefly, to establish a VPN on an MPLS network, each of the LERs participating in the VPN will implement a Virtual Routing and Forwarding (VRF) table. The VRF is used to hold routes for the VPN. A routing protocol such as interior Border Gateway Protocol (iBGP) is used within the MPLS network to exchange routing information between the VRFs. When an edge node learns a route from a customer, e.g. via external BGP (e-BGP), the VRF will export the route via iBGP to the other VRFs on the VPN according to the route export policy for the VRF. When a VRF receives a route it will import the route according to its route import policy. VRFs will thus install routing information to be used for forwarding traffic on the VPN.
When a packet is received at the ingress to the MPLS network, the ingress LER will determine the correct VRF to be used to route the packet across the MPLS network and perform an IP lookup in the VRF to determine the next hop for the packet. The ingress LER will obtain a label for the packet and forward the packet onto the LSP through the MPLS network. The ingress LER may also assign an inner label that will allow the correct VRF to be identified at the egress LER. Since IP VPNs are prevalent on MPLS networks, and link state protocol controlled Ethernet networks are able to be integrated to work with or instead of IP or MPLS networks, it would be advantageous to allow IP VPNs to be implemented on a link state protocol controlled Ethernet network.